package 中等.动态规划.子序列;

import java.util.*;

/**
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/subsets-ii
 */
public class 子集II_90 {

    public static void main(String[] args) {

        System.out.println(subsetsWithDup2(new int[]{1, 2, 3}));

    }

    /**
     * 状态DP + 哈希表
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Set<String> set = new HashSet<>();
        int n = (int) Math.pow(2, nums.length) - 1;
        for (int i = 0; i <= n; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < nums.length; j++) {
                if ((i >> j & 1) == 1) {
                    list.add(nums[j]);
                }
            }
            list.sort((a, b) -> a - b);
            String str = list.toString();
            if (!set.contains(str)) {
                set.add(str);
                lists.add(list);
            }
        }
        return lists;
    }

    /**
     * 动态规划+排序
     * 因为对于子集 [0,2] 和 [2,0] ，判断是重复的，可以对原数组进行排序
     * dp[i] 表示以 [j,i] 结尾的全部子集，j 索引为 i 之前相邻的与nums[i]
     * 不相等的第一个索引
     * dp[i] = dp[0,j] + nums[j+1,i]
     */
    public static List<List<Integer>> subsetsWithDup2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>>[] dp = new List[nums.length];
        List<List<Integer>> lists0 = new ArrayList<>();
        List<Integer> list0 = new ArrayList<>();
        list0.add(nums[0]);
        lists0.add(list0);
        dp[0] = lists0;

        for (int i = 1; i < nums.length; i++) {
            List<List<Integer>> curLists = new ArrayList<>();

            int j = i - 1;
            while (j >= 0 && nums[j] == nums[i]) {
                j--;
            }
            List<Integer> curList = new ArrayList<>();
            for (int r = j + 1; r <= i; r++) {
                curList.add(nums[r]);
            }
            curLists.add(curList);

            for (int r = 0; r <= j; r++) {
                for (List<Integer> list : dp[r]) {
                    List<Integer> cur2List = new ArrayList<>();
                    cur2List.addAll(list);
                    cur2List.addAll(curList);
                    curLists.add(cur2List);
                }
            }

            dp[i] = curLists;
        }

        List<List<Integer>> lists = new ArrayList<>();
        lists.add(new ArrayList<>());
        for (List<List<Integer>> list : dp) {
            lists.addAll(list);
        }
        return lists;
    }

}
